package com.leetcode.题库.score1;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.题库.score1
 * @Author: lei
 * @CreateTime: 2024-03-25  22:32
 * @Description: TODO
 * @Version: 1.0
 */
public class 滑动窗口最大值 {
    public static void main(String[] args) {
        int[] nums = {1, -1};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        int left = 0, right = 0;
        int[] resultInts = new int[nums.length - k + 1];
        while (right < nums.length) {
            while (!linkedList.isEmpty() && right - linkedList.getFirst() >= k) {
                linkedList.removeFirst();
            }
            while (!linkedList.isEmpty() && nums[right] > nums[linkedList.getLast()]) {
                linkedList.removeLast();
            }
            linkedList.add(right);
            if (right - left >= k - 1) {
                resultInts[left] = nums[linkedList.getFirst()];

                left++;
            }
            right++;
        }
        return resultInts;

    }
}
